#include "ArbolHuffman.h"
#include <iostream>
#include <cstring>

using namespace std;

ArbolHuffman::ArbolHuffman() {
	memset(indiceCaracteres, 0, TAM_ALFABETO*sizeof(NodoArbolHuffman*));
	nyt = new NodoArbolHuffman(0, 513, 256, 0); // Nodo NYT de frecuencia 0
	raiz = nyt;
	nodosOrdenados = new ListaDeNodosOrdenados();
	nodosOrdenados->agregarNodo(raiz);
	indiceCaracteres[256] = raiz;
}

// Recibe un caracter y emite su código. Actualiza el arbol
void ArbolHuffman::codificarCaracter(unsigned int caracter) {
	NodoArbolHuffman* nodo = 0;
	if ((nodo = indiceCaracteres[caracter]) != 0) {
		this->enviarCodigo(nodo);
		this->actualizar(nodo);
	} else {
		this->enviarCodigo(nyt);
		nodo = agregarCaracter(caracter); // Devuelve el padre del nodo nuevo
		actualizar(nodo);
		for (int i = 7; i >= 0; i--) {
			punteroHandlerOutput->siguienteBitEsUno(((unsigned char)caracter>>i)&0x01);
		}
	}
}

// Recibe un bit y devuelve un caracter si llegó a una hoja del árbol.
// En caso contrario, devuelve 0 (null).
unsigned char ArbolHuffman::decodificarCaracter() {
	NodoArbolHuffman* nodoActual = this->raiz;
	unsigned char caracterSalida = 0;
	while (nodoActual != this->nyt && nodoActual->caracter == NYT ) {
		// Mientras estemos en un nodo interno nos movemos hacia las hojas...
		if (punteroHandlerInput->siguienteBitEsUno())
			nodoActual = nodoActual->derecha;
		else
			nodoActual = nodoActual->izquierda;
	}
	if (nodoActual == this->nyt) {
		// Tengo que devolver el caracter sin comprimir
		// Agarro 8 bytes que representan bits en binario y los convierto a un byte
		for (int i = 8; i > 0; i--) {
			if (punteroHandlerInput->siguienteBitEsUno()) {
				caracterSalida = caracterSalida | (0x01 << (i-1));
			}
		}
		nodoActual = agregarCaracter(caracterSalida);
	} else {
		caracterSalida = nodoActual->caracter;
	}
	this->actualizar(nodoActual);
	return caracterSalida;
}

// Recorre el arbol desde la raiz hasta el nodo y manda el código (al reves).
void ArbolHuffman::enviarCodigo(NodoArbolHuffman* nodo) {
	bool codigo[32];
	int contador = -1;
	while (nodo != raiz) {
		contador++;
		codigo[contador] = nodo->paridad;
		nodo = nodo->padre;
	}
	while (contador >= 0) {
		punteroHandlerOutput->siguienteBitEsUno(codigo[contador]);
		contador--;
	}
}

// Agrega un nuevo caracter al arbol.
NodoArbolHuffman* ArbolHuffman::agregarCaracter(unsigned int caracter) {
	// Creo dos hojas (la del nuevo caracter y la del nuevo NYT)
	// cuyo padre es el viejo nodo NYT
	NodoArbolHuffman* hijoIzquierda = new NodoArbolHuffman(nyt, nyt->numero-2, 256, 0);
	indiceCaracteres[256] = hijoIzquierda;
	NodoArbolHuffman* hijoDerecha = new NodoArbolHuffman(nyt, nyt->numero-1, caracter, 1);
	indiceCaracteres[caracter] = hijoDerecha;
	nyt->izquierda = hijoIzquierda;
	hijoIzquierda->paridad = 0;
	nyt->derecha = hijoDerecha;
	hijoDerecha->paridad = 1;
	nodosOrdenados->agregarNodo(hijoDerecha);
	nodosOrdenados->agregarNodo(hijoIzquierda);
	nyt->frecuencia++;
	hijoDerecha->frecuencia++;
	nyt = hijoIzquierda;
	return hijoDerecha->padre;
}

void ArbolHuffman::actualizar(NodoArbolHuffman* nodo) {
	while (nodo != raiz) {
		NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = nodosOrdenados->buscarMaxEnBloque(nodo);
		if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->padre)) {
			// Intercambio de nodos para poder incrementar la frecuencia luego
			// y que siga cumpliendo con la Sibling Property
			this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
		}
		nodo->frecuencia++;
		nodo = nodo->padre;
	}
}


// Intercambia dos nodos de igual frecuencia
void ArbolHuffman::intercambiarNodos(NodoArbolHuffman* nodo, NodoArbolHuffman* nodoMaximo) {
	this->nodosOrdenados->intercambiarNodos(nodo->numero, nodoMaximo->numero);
	NodoArbolHuffman* nodoPadre = nodo->padre;
	NodoArbolHuffman* nodoPadreMaximo = nodoMaximo->padre;
	if (nodoPadre->izquierda == nodo) {
		nodoPadre->izquierda = nodoMaximo;
		nodoMaximo->paridad = 0;
	} else {
		nodoPadre->derecha = nodoMaximo;
		nodoMaximo->paridad = 1;
	}
	nodoMaximo->padre = nodoPadre;
	if (nodoPadreMaximo->derecha == nodoMaximo) {
		nodoPadreMaximo->derecha = nodo;
		nodo->paridad = 1;
	} else {
		nodoPadreMaximo->izquierda = nodo;
		nodo->paridad = 0;
	}
	nodo->padre = nodoPadreMaximo;
	// Ahora quiero intercambiar los numeros de los nodos
	unsigned int numeroTemp = nodo->numero;
	nodo->numero = nodoMaximo->numero;
	nodoMaximo->numero = numeroTemp;
}

void ArbolHuffman::setBitHandlerInput(BitHandlerInput& bhi) {
	punteroHandlerInput = &bhi;
}

void ArbolHuffman::setBitHandlerOutput(BitHandlerOutput& bho) {
	punteroHandlerOutput = &bho;
}


ArbolHuffman::~ArbolHuffman() {
    delete this->nodosOrdenados;
}
